/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/the-skyline-problem
   @Language: C++
   @Datetime: 20-01-09 16:57
   */

class Solution {
public:
	vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
		vector<pair<int,int> > xys;
		for(const auto &b:buildings){
			xys.push_back({b[0], -b[2]});
			xys.push_back({b[1], b[2]});
		}
		sort(xys.begin(), xys.end());
		multiset<int> heights({0});
		vector<vector<int> > vs;
		int height=0;
		for(const auto &xy:xys){
			if (xy.second<0) heights.insert(-xy.second);
			else heights.erase(heights.find(xy.second));
			int maxh = *heights.rbegin();
			if (height!=maxh){
				vs.push_back({xy.first, maxh});
				height=maxh;
			}
		}
		return vs;
	}
};
